package main

import (
	"bufio"
	"bytes"
	"encoding/binary"
	"fmt"
	"os"
)

type Image struct {
	image   []byte
	history *bytes.Buffer
	road    []byte
	id      int
	pid     int
}

func NewImage() *Image {
	var image Image
	// image.image = []byte{0, 6, 2, 3, 6, 7, 4, 5, 7, 6, 8, 9, 6, 7, 1, 1, 7, 1, 0, 0, 1}
	// image.road = []byte{18, 19}
	image.image = []byte{0, 1, 2, 3, 1, 6, 4, 5, 6, 7, 6, 0, 7, 1, 7, 0, 1, 8, 9, 8, 9}
	image.road = []byte{11, 15}

	image.history = new(bytes.Buffer)
	image.id = 1
	image.pid = 0
	return &image
}

func NewImageFrFile(path string) (*Image, error) {
	file, err := os.Open(path)
	if err != nil {
		return nil, err
	}
	scanner := bufio.NewScanner(file)
	scanner.Scan()
	var image = Image{
		image: scanner.Bytes(),
		road:  []byte{0, 0},
	}
	for i := 1; i != 21; i++ {
		if image.image[i] == 0 {
			if image.road[0] != 0 {
				image.road[1] = byte(i)
			} else {
				image.road[0] = byte(i)
			}
		}
	}
	scanner.Scan()
	image.history = bytes.NewBuffer(scanner.Bytes())
	return &image, nil
}
func (i *Image) Save2File(path string) error {
	file, err := os.OpenFile(path, os.O_RDWR|os.O_CREATE, 0644)
	defer file.Close()
	if err != nil {
		return err
	}
	_, err = file.Write(i.image)
	_, err = file.Write(i.history.Bytes())
	return err
}
func (i *Image) GetPosition(x, y int) int {
	p := (x-1)*4 + y
	if p > 20 || p < 1 {
		return -1
	}
	if i.image[p] == 3 || i.image[p] == 9 {
		return left(p)
	}
	if i.image[p] == 4 || i.image[p] == 7 {
		return up(p)
	}
	if i.image[p] == 5 {
		return left(up(p))
	}
	return p
}
func (i *Image) Move(position int, action string) bool {
	if position < 1 || position > 20 || position == int(i.road[0]) || position == int(i.road[1]) {
		return false
	}
	switch action {
	case "u":
		u := up(position)
		if u == -1 || i.image[u] != 0 {
			return false
		}
		if i.image[position] == 2 || i.image[position] == 8 {
			pr := right(position)
			ru := up(pr)
			if ru == -1 || pr == -1 || i.image[ru] != 0 {
				return false
			}
			i.image[u] = i.image[position]
			i.image[ru] = i.image[pr]
			if i.image[position] == 2 {
				d := down(position)
				dr := right(d)
				if d == -1 || dr == -1 {
					return false
				}
				i.image[position] = i.image[d]
				i.image[pr] = i.image[dr]
				i.image[d] = 0
				i.image[dr] = 0
				i.road[0] = byte(d)
				i.road[1] = byte(dr)
				return true
			}
			i.image[position] = 0
			i.image[pr] = 0
			i.road[0] = byte(position)
			i.road[1] = byte(pr)
			return true
		}
		i.image[u] = i.image[position]
		if i.image[position] == 6 {
			d := down(position)
			if d == -1 {
				return false
			}
			i.image[position] = i.image[d]
			i.image[d] = 0
			if i.road[0] == byte(u) {
				i.road[0] = byte(d)
			} else {
				i.road[1] = byte(d)
			}
			return true
		}
		i.image[position] = 0
		if i.road[0] == byte(u) {
			i.road[0] = byte(position)
		} else {
			i.road[1] = byte(position)
		}
		return true
	case "d":
		if i.image[position] == 2 || i.image[position] == 6 {
			position = down(position)
			if position == -1 {
				return false
			}
		}
		d := down(position)
		if d == -1 || i.image[d] != 0 {
			return false
		}
		if i.image[position] == 4 || i.image[position] == 8 {
			pr := right(position)
			dr := right(d)
			if dr == -1 || i.image[dr] != 0 || pr == -1 {
				return false
			}
			i.image[d] = i.image[position]
			i.image[dr] = i.image[pr]
			if i.image[position] == 4 {
				u := up(position)
				ur := right(u)
				if u == -1 || ur == -1 {
					return false
				}
				i.image[position] = i.image[u]
				i.image[pr] = i.image[ur]
				i.image[u] = 0
				i.image[ur] = 0
				i.road[0] = byte(u)
				i.road[1] = byte(ur)
				return true
			}
			i.image[position] = 0
			i.image[pr] = 0
			i.road[0] = byte(position)
			i.road[1] = byte(pr)
			return true
		}
		i.image[d] = i.image[position]
		if i.image[position] == 7 {
			u := up(position)
			if u == -1 {
				return false
			}
			i.image[position] = i.image[u]
			i.image[u] = 0
			if i.road[0] == byte(d) {
				i.road[0] = byte(u)
			} else {
				i.road[1] = byte(u)
			}
			return true
		}
		i.image[position] = 0
		if i.road[0] == byte(d) {
			i.road[0] = byte(position)
		} else {
			i.road[1] = byte(position)
		}
		return true
	case "l":
		l := left(position)
		if l == -1 || i.image[l] != 0 {
			return false
		}
		if i.image[position] == 2 || i.image[position] == 6 {
			d := down(position)
			dl := left(d)
			if d == -1 || dl == -1 || i.image[dl] != 0 {
				return false
			}
			i.image[l] = i.image[position]
			i.image[dl] = i.image[d]
			if i.image[position] == 2 {
				pr := right(position)
				dr := right(d)
				if pr == -1 || dr == -1 {
					return false
				}
				i.image[position] = i.image[pr]
				i.image[d] = i.image[dr]
				i.image[pr] = 0
				i.image[dr] = 0
				i.road[0] = byte(pr)
				i.road[1] = byte(dr)
				return true
			}
			i.image[position] = 0
			i.image[d] = 0
			i.road[0] = byte(position)
			i.road[1] = byte(d)
			return true
		}
		i.image[l] = i.image[position]
		if i.image[position] == 8 {
			pr := right(position)
			if pr == -1 {
				return false
			}
			i.image[position] = i.image[pr]
			i.image[pr] = 0
			if i.road[0] == byte(l) {
				i.road[0] = byte(pr)
			} else {
				i.road[1] = byte(pr)
			}
			return true
		}
		i.image[position] = 0
		if i.road[0] == byte(l) {
			i.road[0] = byte(position)
		} else {
			i.road[1] = byte(position)
		}
		return true
	case "r":
		if i.image[position] == 2 || i.image[position] == 8 {
			position = right(position)
			if position == -1 {
				return false
			}
		}
		pr := right(position)
		if pr == -1 || i.image[pr] != 0 {
			return false
		}
		if i.image[position] == 3 || i.image[position] == 6 {
			d := down(position)
			dr := right(d)
			if dr == -1 || i.image[dr] != 0 || d == -1 {
				return false
			}
			i.image[pr] = i.image[position]
			i.image[dr] = i.image[d]
			if i.image[position] == 3 {
				l := left(position)
				ld := down(l)
				if l == -1 || ld == -1 {
					return false
				}
				i.image[position] = i.image[l]
				i.image[d] = i.image[ld]
				i.image[l] = 0
				i.image[ld] = 0
				i.road[0] = byte(l)
				i.road[1] = byte(ld)
				return true
			}
			i.image[position] = 0
			i.image[d] = 0
			i.road[0] = byte(position)
			i.road[1] = byte(d)
			return true
		}
		i.image[pr] = i.image[position]
		if i.image[position] == 9 {
			l := left(position)
			if l == -1 {
				return false
			}
			i.image[position] = i.image[l]
			i.image[l] = 0
			if i.road[0] == byte(pr) {
				i.road[0] = byte(l)
			} else {
				i.road[1] = byte(l)
			}
			return true
		}
		i.image[position] = 0
		if i.road[0] == byte(pr) {
			i.road[0] = byte(position)
		} else {
			i.road[1] = byte(position)
		}
		return true
	default:
		return false
	}
	return true
}
func (i *Image) Byte() []byte {
	return i.image
}
func (i *Image) IsWin() bool {
	return binary.BigEndian.Uint16(i.image[18:18+2]) == 1029
}
func (i *Image) Clone() *Image {
	var ni Image
	ni.history = bytes.NewBuffer(i.history.Bytes())
	ni.id = i.id
	ni.pid = i.pid
	ni.image = make([]byte, 21, 21)
	copy(ni.image, i.image)
	ni.road = make([]byte, 2, 2)
	copy(ni.road, i.road)
	return &ni
}
func (i *Image) draw() {
	b := i.image
	fmt.Println("\033[0m++++++")
	for idx := 1; idx < 21; idx++ {
		if idx%4 == 1 {
			fmt.Print("\033[0m+")
		}
		if b[idx] == 0 {
			fmt.Printf("\033[%dm ", colourMap[b[idx]])
		} else {
			fmt.Printf("\033[%dm*", colourMap[b[idx]])
		}
		if idx%4 == 0 {
			fmt.Println("\033[0m+")
		}
	}
	fmt.Println("\033[0m++++++")
}

type ImageSet struct {
	set map[string]struct{}
}

func NewImageSet() *ImageSet {
	var imageSet ImageSet
	imageSet.set = make(map[string]struct{})
	return &imageSet
}
func (imageSet *ImageSet) Has(image *Image) bool {
	if _, ok := imageSet.set[string(image.Byte())]; !ok {
		return false
	}
	return true
}
func (imageSet *ImageSet) Set(image *Image) {
	imageSet.set[string(image.Byte())] = struct{}{}
}

type ImageQueue []*Image

func (q *ImageQueue) Push(n *Image) {
	*q = append(*q, n)
}
func (q *ImageQueue) Pop() (n *Image) {
	if q.Len() == 0 {
		return nil
	}
	n = (*q)[0]
	*q = (*q)[1:]
	return
}
func (q *ImageQueue) Len() int {
	return len(*q)
}

func up(position int) int {
	if position > 20 || position < 5 {
		return -1
	}
	return position - 4
}
func down(position int) int {
	if position > 16 || position < 1 {
		return -1
	}
	return position + 4
}
func left(position int) int {
	if position < 1 || position > 20 {
		return -1
	}
	if (position-1)%4 == 0 {
		return -1
	}
	return position - 1
}
func right(position int) int {
	if position < 1 || position > 20 {
		return -1
	}
	if (position-4)%4 == 0 {
		return -1
	}
	return position + 1
}
func autoMove(image *Image) bool {
	qStatus := new(ImageQueue)
	setStatus := NewImageSet()
	qStatus.Push(image.Clone())
	setStatus.Set(image)
	j := 1
	for tImage := qStatus.Pop(); tImage != nil; tImage = qStatus.Pop() {

		for x := 1; x != 6; x++ {
			for y := 1; y != 6; y++ {
				p := tImage.GetPosition(x, y)
				tclone := tImage.Clone()
				if tclone.Move(p, "u") {
					if !setStatus.Has(tclone) {
						tclone.pid = tImage.id
						j++
						tclone.id = j
						setStatus.Set(tclone)
						qStatus.Push(tclone)
						tclone.history.Write([]byte{'(', '0' + byte(x), ',', '0' + byte(y), ',', 'u', ')', '\n'})
						if tclone.IsWin() {
							return true
						}
					}
				}

				tclone = tImage.Clone()
				if tclone.Move(p, "d") {
					if !setStatus.Has(tclone) {
						tclone.pid = tImage.id
						j++
						tclone.id = j
						setStatus.Set(tclone)
						qStatus.Push(tclone)
						tclone.history.Write([]byte{'(', '0' + byte(x), ',', '0' + byte(y), ',', 'd', ')', '\n'})
						if tclone.IsWin() {
							fmt.Println(tclone.history)
							return true
						}
					}
				}

				tclone = tImage.Clone()
				if tclone.Move(p, "l") {
					if !setStatus.Has(tclone) {
						tclone.pid = tImage.id
						j++
						tclone.id = j
						setStatus.Set(tclone)
						qStatus.Push(tclone)
						tclone.history.Write([]byte{'(', '0' + byte(x), ',', '0' + byte(y), ',', 'l', ')', '\n'})
						if tclone.IsWin() {
							fmt.Println(tclone.history)
							return true
						}
					}
				}

				tclone = tImage.Clone()
				if tclone.Move(p, "r") {
					if !setStatus.Has(tclone) {
						tclone.pid = tImage.id
						j++
						tclone.id = j
						setStatus.Set(tclone)
						qStatus.Push(tclone)
						tclone.history.Write([]byte{'(', '0' + byte(x), ',', '0' + byte(y), ',', 'r', ')', '\n'})
						if tclone.IsWin() {
							fmt.Println(tclone.history)
							return true
						}
					}
				}

			}
		}
	}
	return false
}
func init() {
	fmt.Printf("\033[%dm*\033[0m: 4*4\n", colourMap[2])
	fmt.Printf("\033[%dm*\033[0m: 1*1\n", colourMap[1])
	fmt.Printf("\033[%dm*\033[0m: 2*1\n", colourMap[6])
	fmt.Printf("\033[%dm*\033[0m: 1*2\n", colourMap[8])
	fmt.Println("1. input  x y action to move, such as 3 2 r which means choose the position(3, 2) to move right a cell")
	fmt.Println("2. input save to save the status")
	fmt.Println("3. input load to load the exist status")
	fmt.Println("4. input exit to exit")
	fmt.Print(ENTER_STR)
}

func main() {
	initImage := NewImage()
	initImage.draw()
	cleanCmd(7)
	for {
		cmd = nextString()
		if !parseCmd(cmd) {
			fmt.Printf("\033[%dA\r\033[%dC\033[K", 1, len(ENTER_STR))
			continue
		}
		switch action {
		case "save":
			err := initImage.Save2File("./temp.hrd")
			if err != nil {
				fmt.Println(err.Error())
			}
			initImage.draw()
			return
		case "load":
			tempImage, err := NewImageFrFile("./temp.hrd")
			if err == nil {
				initImage = tempImage
			}
		case "cheat":
			if autoMove(initImage) {
				return
			}
		case "exit":
			initImage.draw()
			return
		default:
			p := initImage.GetPosition(x, y)
			initImage.Move(p, action)
		}
		initImage.draw()
		cleanCmd(8)
	}
}
